#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#include "NativeMath.h"

/*
* This method calculates the sum of two integers encoded using
* two's ciomplement and stored as UINT32 arrays. The result of the
* calculation is placed in the integer pointed to by the 'r'
* parameter. The user must make sure that 'r' is LONG enough to 
* accommodate the result. Alternativly 'r' may reference null in 
* which case the method will allocate memory.
*/
void addinternal2(const uintarray* a, const UINT b, uintarray* result)
{
	UINT carry;
	//uintarray* result;
	ULONG t;
	int i;

	//if(r == NULL)
	//	result = calloc(a->length + 1, sizeof(UINT));
	//else
	//	result = r;

	t = (ULONG)a->values[0] + (ULONG)b;
	carry = (UINT)(t >> BASE_TYPE_BITS);
	result->values[0] = (UINT)t;


	for (i = 1; i < a->length; i++)
	{
		t = (ULONG)a->values[i] + (ULONG)carry;
		carry = (UINT)(t >> BASE_TYPE_BITS);
		result->values[i] = (UINT)t;
	}

	if (i < result->length)
		result->values[i] = carry;
}

/*
* This method calculates the sum of two integers encoded using 
* two's complement and stored as UINT32 arrays. The result of the 
* calculation is placed in the integer pointed to by the reference 
* parameter 'result'. This algorithm can handle situations where the 
* three input arrays have different lengths.
*/
static void addinternal(const uintarray* a, const BOOL a_signed, const uintarray* b, const BOOL b_signed, const uintarray* result) 
{
	/* index variable, used to traverse the three arrays */
	int i = 0; 
	UINT carry = 0;

	/*
	* Since the three input arrays may have different lengths we must			
	* must make sure that we do not read or write beyond any of the three.
	* Instead of testing the length of each of the three arrays in the 
	* algorithm loop we compare the widths of the arrays first and then
	* apply a special, adapted version, of the two's complement addition
	* algorithm. 
	*/ 
	if (a->length <= b->length)
	{
		if(result->length <= a->length) /* r.len < a.len < b.len */
		{
			for(; i < result->length; i++)
			{
				LONG t = (LONG)(a->values[i]) + (LONG)(b->values[i]) + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
		else if(b->length <= result->length) /* r.len > b.len > a.len */
		{
			for(i = 0; i < a->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)b->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			/*
			* if the length of a is signed and negative
			* it is necessary to "manually" include extra sign bits while performing the
			* rest of the addition.
			*/
			if (a_signed && ((a->values[a->length - 1] & (1 << (BASE_TYPE_BITS - 1))) != 0))
			{
				for (; i < b->length; i++)
				{
					LONG t = (LONG)b->values[i] + (LONG)BASE_MAX_VALUE + (LONG)carry;
					carry = (UINT)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}
			else
			{
				for (; i < b->length; i++)
				{
					LONG t = (LONG)carry + (LONG)b->values[i];
					carry = (UINT)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}

			/* Carry is either 0 or 1 */
			if (i < result->length)
				result->values[i] = carry;

			return;
		}
		else /*  b.len > r.len > a.len */
		{
			for (i = 0; i < a->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)b->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			for (; i < result->length; i++)
			{
				LONG t = (LONG)carry + (LONG)b->values[i];
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}        
	}
	else /* a.Length > b.Length */
	{
		if (result->length >= a->length) /* r.len > a.len > b.len */
		{
			for (; i < b->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)b->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			/*
			* if the length of b (the number being subtracted) is signed and negative
			* it is necessary to "manually" include extra sign bits while performing the
			* rest of the addition.
			*/
			if (b_signed && ((b->values[b->length - 1] & (1 << (BASE_TYPE_BITS - 1))) != 0))
			{
				for (; i < a->length; i++)
				{
					LONG t = (LONG)a->values[i] + (LONG)BASE_MAX_VALUE + (LONG)carry;
					carry = (UINT)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}
			else
			{
				for (; i < a->length; i++)
				{
					LONG t = (LONG)a->values[i] + (LONG)carry;
					carry = (UINT)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}

			if(i < result->length)          
				result->values[i] = carry;                     

			return;
		}
		else if (b->length >= result->length)  /* a.len > b.len > r.len */
		{
			for (; i < result->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)b->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
		else /* a.len > r.len > b.len */
		{
			for (; i < b->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)b->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			for (; i < result->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
	}
}

EXPORT void add(const ninteger* a, const ninteger* b, const ninteger* result)
{
	addinternal(a->content, a->issigned, b->content, b->issigned, result->content);

	if(!result->issigned) 
	{
		if(result->width % BASE_TYPE_BITS != 0)
		{
			result->content->values[result->content->length - 1] &= bitmasks[result->width % BASE_TYPE_BITS];
		}
	} 
	else
	{
		signextend(result, result->width - 1);
	}
}

/*
* Given the integers (a[m-1],...,a[1],a[0]) and (b[n-1],...,b[1],b[0]) this method
* return their difference.
*/
void subinternal(const uintarray* a, const BOOL a_signed, const uintarray* b, const BOOL b_signed, const uintarray* result) 
{
	int i = 0; /* index variable */
	int carry = 0; 

	/*
	* Since the three input arrays may have different lengths we must			
	* must make sure that we do not read or write beyond any of the three.
	* Instead of testing the length of each of the three arrays in the 
	* algorithm loop we compare the widths of the arrays first and then
	* apply a special, adapted version, of the two's complement addition
	* algorithm. 
	*/ 

	if (a->length <= b->length)
	{
		if(result->length <= a->length) /* r.len < a.len < b.len */
		{
			for(; i < result->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
		else if(b->length <= result->length) /* r.len > b.len > a.len */
		{
			for(i = 0; i < a->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			for(; i < b->length; i++)
			{
				LONG t = (LONG)carry - (LONG)b->values[i];
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			/* Carry is either 0 or -1 */
			for(; i < result->length; i++)                    
				result->values[i] = (UINT) carry;

			return;
		}
		else /* b.len > r.len > a.len */
		{
			for (i = 0; i < a->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			for (; i < result->length; i++)
			{
				LONG t = (LONG)carry - (LONG)b->values[i];
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}        
	}
	else /* a.Length > b.Length */
	{
		if (result->length >= a->length) /* r.len > a.len > b.len */
		{
			for (; i < b->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			/*
			* if the length of b (the number being subtracted) is signed and negative
			* it is necessary to "manually" include extra sign bits while performing the
			* rest of the subtraction.
			*/
			if (b_signed && ((b->values[b->length - 1] & (1 << (BASE_TYPE_BITS - 1))) != 0))
			{
				for (; i < a->length; i++)
				{
					LONG t = (LONG)a->values[i] - (LONG)BASE_MAX_VALUE + (LONG)carry;
					carry = (int)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}
			else
			{
				for (; i < a->length; i++)
				{
					LONG t = (LONG)a->values[i] + (LONG)carry;
					carry = (int)(t >> BASE_TYPE_BITS);
					result->values[i] = (UINT)t;
				}
			}

			for (; i < result->length; i++)          
				result->values[i] = (UINT) carry;                     

			return;
		}
		else if (b->length >= result->length)  /* a.len > b.len > r.len */
		{
			for (; i < result->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
		else // a.len > r.len > b.len
		{
			for (; i < b->length; i++)
			{
				LONG t = (LONG)a->values[i] - (LONG)b->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			for (; i < result->length; i++)
			{
				LONG t = (LONG)a->values[i] + (LONG)carry;
				carry = (int)(t >> BASE_TYPE_BITS);
				result->values[i] = (UINT)t;
			}

			return;
		}
	}
}

EXPORT void sub(const ninteger* a, const ninteger* b, const ninteger* result)
{
	subinternal(a->content, a->issigned, b->content, b->issigned, result->content);

	if(!result->issigned) 
	{
		if(result->width % BASE_TYPE_BITS != 0)
		{
			result->content->values[result->content->length - 1] &= bitmasks[result->width % BASE_TYPE_BITS];
		}
	} 
	else
	{
		signextend(result, result->width - 1);
	}
}

/*
* Multiply the unsigned integers a and b leaving the result in 
* the integer pointed to by r. Note: this method cannot handle sign.
*/
void mulinternal2(const uintarray* a, const UINT b, const uintarray* r) 
{
	/* Result of multiplication can be as wide as len(a) + len(b) */

	/* This implementation of multiply cannot handle the situation where
	* the same array is specified as the result and one or both of the 
	* argument arrays.
	*/

	UINT carry = 0;
	uintarray* result;
	ULONG t;
	int i;

	assert(r != NULL);
	if(r == a)
	{
		result = alloc_uintarr(r->length);
	} 
	else
	{
		result = r;
	}

	for (i = 0; i < a->length; i++)
	{
		t = (ULONG)a->values[i] * (ULONG)b + (ULONG)result->values[i] + (ULONG)carry;
		carry = (UINT)(t >> BASE_TYPE_BITS);

		if (i < result->length)
			result->values[i] = (UINT)t;
	}

	if(r == a)
	{
		memcpy(r->values, result->values, r->length * sizeof(UINT));
		free_uintarr(result);
	}
}

/*
* Multiply the unsigned integers a and b leaving the result in 
* the integer pointed to by r. Note: this method cannot handle sign.
*/
void mulinternal(const uintarray* a, const uintarray* b, const uintarray* result) 
{
	/* Result of multiplication can be as wide as len(a) + len(b) */

	/* This implementation of multiply cannot handle the situation where
	* the same array is specified as the result and one or both of the 
	* argument arrays.
	*/

	UINT carry = 0;
	ULONG t;
	int i, j;

	assert(result != NULL);
	assert(result != a || result != b);

	for(i = 0; i < a->length; i++)
	{
		for(j = 0; j < b->length; j++)
		{
			/* avoid writing beyond the end of the result array */
			if (j + i < result->length)
			{
				t = (ULONG)a->values[i] * (ULONG)b->values[j] + (ULONG)result->values[i + j] + (ULONG)carry;
				carry = (UINT)(t >> BASE_TYPE_BITS);
				result->values[i + j] = (UINT)t;
			}
		}
	}
}

EXPORT void mul(const ninteger* a, const ninteger* b, const ninteger* result)
{
	BOOL sign = a->issigned || b->issigned;

	BOOL a_negative = isnegative(a);
	BOOL b_negative = isnegative(b);

	uintarray* ar = NULL;
	uintarray* br = NULL;

	if (a_negative)
	{
		ar = alloc_uintarr(a->content->length);
		negateinternal(a->content, ar);
	}
	else
	{
		ar = a->content;
	}

	if (b_negative)
	{
		br = alloc_uintarr(b->content->length);
		negateinternal(b->content, br);
	}
	else
	{
		br = b->content;
	}

	mulinternal(ar, br, result->content);

	if (a_negative ^ b_negative)
		negateinternal(result->content, result->content);

	/* dealloc arrays */
	if(ar != a->content)
	{
		free_uintarr(ar);
	}
	if(br != b->content)
	{
		free_uintarr(br);
	}
}

/* Divide the long integer a by the single digit integer b. Note:
* this method cannot handle sign.
*/
void divinternal2(uintarray** r, UINT* remainder, const uintarray* a, UINT b)
{
	uintarray* result = alloc_uintarr(a->length);

	ULONG t = 0;
	int i = a->length - 1;

	*remainder = 0;

	do
	{
		t = ((ULONG)(*remainder) << BASE_TYPE_BITS) + (ULONG)a->values[i];
		*remainder = (UINT)(t % b);
		result->values[i] = (UINT)(t / b);
	} while (--i >= 0);

	if((*r) != NULL)
		free_uintarr(*r);

	*r = result;
}


void divinternal(uintarray** result, uintarray** remainder, uintarray* a, uintarray* b)
{
	assert(FALSE); /* not implemented */
}


EXPORT void divide(const ninteger* a, const ninteger* b, ninteger** result)
{
	BOOL sign = a->issigned || b->issigned;
	BOOL a_negative = isnegative(a);
	BOOL b_negative = isnegative(b);

	uintarray* ar = NULL;
	uintarray* br = NULL;

	if (a_negative)
	{
		ar = alloc_uintarr(a->content->length);
		negateinternal(a->content, ar);
	}
	else
	{
		ar = a->content;
	}

	if (b_negative)
	{
		br = alloc_uintarr(b->content->length);
		negateinternal(b->content, br);
	}
	else
	{
		br = b->content;
	}

	/* check for division by zero */
	if (iszeroarr(b->content))
		perror("division by zero");

	if (br->length == 1)
	{
		UINT remainder = 0;
		// use short division if possible
		uintarray* ref = (*result)->content;
		divinternal2(&((*result)->content), &remainder, ar, br->values[0]);
	}
	else
	{
		uintarray* remainder = NULL;
		//divinternal(result.content, &remainder, ar, br);
	}

	if (a_negative ^ b_negative)  
	{
		uintarray* ref = (*result)->content; 
		negateinternal(ref, ref);
	}

	/* dealloc arrays */
	if(ar != a->content)
	{
		free_uintarr(ar);
	}
	if(br != b->content)
	{
		free_uintarr(br);
	}
}